package leetcode.code0414;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution extends Solution414 {

	public int thirdMax1(int[] nums) {
		Set<Integer> set = new HashSet<>();
		for (int x : nums)
			set.add(x);
		List<Integer> list = new ArrayList<>(set);
		Collections.sort(list);
		return list.size() < 3 ? list.get(list.size() - 1) : list.get(list.size() - 3);
	}

	@Override
	public int thirdMax(int[] nums) {
		Arrays.sort(nums);
		int len = nums.length;
		int max = nums[len - 1];
		boolean mid = false;
		int last = max;
		for (int i = nums.length - 2; i >= 0; i--) {
			if (nums[i] != last) {// 发现一个新数
				if (!mid) {// 没找到第二大呢
					last = nums[i];// 第二大为新数
					mid = true;// 找到第二大了
				} else {
					return nums[i];// 第三大,结束
				}
			}
		}
		return max;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
